package Homework;

// 1、无头单向非循环链表实现
public class SingleLinkedList {
    static class NodeList{
        public int val;
        public NodeList next;

        public NodeList(int val){
            this.val = val;
        }
    }
    public NodeList head;

    public void createList(){
        NodeList node1 = new NodeList(12);
        NodeList node2 = new NodeList(52);
        NodeList node3 = new NodeList(52);
        NodeList node4 = new NodeList(52);
        NodeList node5 = new NodeList(52);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }

    //头插法
    public void addFirst(int data) {
      NodeList newNode = new NodeList(data);
      newNode.next = this.head;
      head = newNode;
    }


    //尾插法
    public void addLast(int data){
        NodeList lastNode = new NodeList(data);
        if(head == null){
            head = lastNode;
        }
        NodeList tmp = this.head;
        while(tmp.next != null){
            tmp = tmp.next;
        }
        tmp.next = lastNode;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if(index < 0 || index > size()){
            return false;
        }
        if(index == 0){
            addFirst(data);
            return true;
        }
        if(index == size()){
            addLast(data);
            return true;
        }
        int c = 0;
        NodeList tmp =this.head;
        while(c != index-1){
            tmp = tmp.next;
            c++;
        }
        NodeList newNode = new NodeList(data);
        newNode.next = tmp.next;
        tmp.next = newNode;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        NodeList tmp = head;
        while(tmp != null){
            if(tmp.val == key){
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }

    //找到要删除的关键字key的前一个节点
    private NodeList findKey(int key){
        NodeList cur = head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
      if(head == null)return;
      if(head.val == key){
          head = head.next;
          return;
      }
      NodeList tmp = findKey(key);
      if(tmp == null)return;
      NodeList del = tmp.next;
      tmp.next = del.next;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
       if(head == null)return;
       NodeList cur = head.next;
       NodeList prev = head;
       while(cur != null){
           if(cur.val == key){
               prev.next = cur.next;
               cur =cur.next;
           }else{
               prev = cur;
               cur = cur.next;
           }
       }
       if(head.val == key){
           head = head.next;
       }
    }
    //得到单链表的长度
    public int size(){
        NodeList tmp = this.head;
        int count = 0;
        while(tmp != null){
            count++;
            tmp = tmp.next;
        }
        return count;
    }
    public void display(){
        NodeList tmp = this.head;
        while(tmp != null){
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        }
    }
    public void clear(){
        head = null;
    }
//    public void clear(){
//        ListKNode cur = head;
//        while(cur != null){
//            ListNode curN = cur.next;
//            cur.prev = null;
//            cur.next = null;
//            cur = curN;
//        }
//        head = last = null;
//    }
}
